Lagrange Relaxation Based Method for the QoS Routing Problem

#optimization #Lagrange-relaxation

本文提出了一种实用高效的 QoS 路由方法，为延迟受限的最小成本路由问题（delay constrained least cost routing problem，DCLC）提供了解决方案。

Features：

• 该算法使用了聚集成本的概念，
• 基于拉格朗日松弛来高效找到最优乘数。
• 给出了理论下界，和最优算法效果接近
• 通过进一步放宽路径的最优性，我们还提供了一种简便的方法来控制算法运行时间与所发现路径质量之间的权衡。

Definition of DCLC Problem

给出一个有向连通图 $G(V,E)$，每条边有非负的 cost $c(e)$ 和 delay $d(e)$

定义源点 $s$ ，目标点 $t$，延时上界 ${\mathrm{\Delta }}_{delay}$，则问题可表示为下面的约束优化（COP）问题：

其中 $P^{\prime }(s,t)$ 是点 $s$ 到 $t$ 的一条满足延时上界限制路径（即 $\sum _{e\in p}d(e)\le {\mathrm{\Delta }}_{delay}$）

Previous Work

。。。（暂时没看）

Proposed ALgorithm

原问题可表示为：

（其中，$P(s,t)$ 是从点 $s$ 到 $t$ 的所有路径组成的集合，$p$ 是某一条路径）

LARAC - Lagrange Relaxation based Aggregated Cost algorithm 基于下面这个公式：

显然：对于一个确定的 $\lambda$ 来说，计算一条 $c_{\lambda }$ 最小的路径 $p_{\lambda }$ 是很容易的。

那么，我们一开始设 $\lambda =0$ 时，如果得到的路径 $p_{\lambda =0}$ 满足 $d(p_{\lambda =0})\le {\mathrm{\Delta }}_{delay}$ ，那么我们就得到了一个最优解；

而如果 $d(p_{\lambda =0})>{\mathrm{\Delta }}_{delay}$ ，那我们就需要增大 $\lambda$ 来提高延时的重要性

现在的问题是：

1. 如何找到最优的 $\lambda$
2. 确定解的近似比

那么，$L(\lambda )$ 是 原问题 的一个下界

要最大化下界，就是要最大化 $L(\lambda )$

Some Properties of the Function $L(\lambda )$

Claim 2：$L$ 是一个凹的分段线性函数，即 $L$ 是 $c(p)+\lambda (d(p)-∆delay)$ 这个线性函数的最小值

Claim 3：定义 $d(p_{\lambda })$ 为函数 $L(\lambda )$ 在 $\lambda$ 这一点的超梯度

Claim 4：对于每一条 $c_{\lambda }$ 最小的路径 $p_{\lambda }$：

1. 若 $\lambda <{\lambda }^{\ast }$ ，则 $d(p_{\lambda })\ge {\mathrm{\Delta }}_{delay}$
2. 若 $\lambda >{\lambda }^{\ast }$ ，则 $d(p_{\lambda })\le {\mathrm{\Delta }}_{delay}$

Claim 5：当前仅当存在使 $c_{{\lambda }^{\ast }}$-minimal 的路径 $p_c$ 和 $p_d$ 满足 $d(p_c)\ge {\mathrm{\Delta }}_{delay}$ 并且 $d(p_d)\le {\mathrm{\Delta }}_{delay}$ 时，${\lambda }^{\ast }$ 是 $L(\lambda )$ 的最大点

Claim 6：若 $0\le {\lambda }_1<{\lambda }_2$，并且 $p_{{\lambda }_1},p_{{\lambda }_2}$ 分别是 λ1-minimal 和 λ2-minimal 路径，则 $c_{p_{{\lambda }_1}}\le c_{p_{{\lambda }_2}}$ 且 $d_{p_{{\lambda }_1}}\ge d_{p_{{\lambda }_2}}$

由 Claim 5 和 Claim 6 可知：使 $L(\lambda )$ 最大的 ${\lambda }^{\ast }$ 是满足条件 “存在 $c_{{\lambda }^{\ast }}$-minimal 路径 $p_d$ 满足延迟约束” 的最小的 ${\lambda }^{\ast }$

总结：这个算法忽略了 constraining conditions，and build them into the object function.

Description of Algorithm

1. 令 $\lambda =0$，求 $c_{\lambda }$-minimal 路径（相当于忽略 delay constraint 直接求最短路），将求得的路径设为 $p_c$
2. 求延迟 $d$ 的最短路，设为 $p_d$
3. 在 repeat 循环中，$d(p_c)>{\mathrm{\Delta }}_{delay}$ ， $d(p_d)\le {\mathrm{\Delta }}_{delay}$ ，是一个类似==二分==的过程
   1. 对于某一个 $\lambda$ ，如果 $p_c$ 和 $p_d$ 都是 $c_{\lambda }$-minimal 的，那么根据 Claim5，这个 $\lambda$ 是 $L(\lambda )$ 的最大值点。
   2. 为什么令 $c_{\lambda }(p_c)=c_{\lambda }(p_d)$，得到的 $\lambda$ 是负数？为什么作者设计算法时用的是绝对值？

Running Time of the Algorithm

时间复杂度为 $O(m^2{\log }^{4}m)$.

Optimality of the Path

这一段没太看懂qwq

• 这个算法找到的是最优的 $\lambda$ ，但不一定是最优的 路径
• 这种情况很容易发生：The modified cost ($c_{\lambda }$) of the optimal path is higher than a suboptimal path at the optimal $\lambda$.
  • 我觉得原因是 $L(\lambda ):=min\{c_{\lambda }(p):p\in P(s,t)\}-\lambda {\mathrm{\Delta }}_{delay}$
• 为了提高这个算法的表现，作者提出可以在 $c_{\lambda }$ 中用 $c^2$ 代替 $c$ （即令 $c_{\lambda }=c^2+\lambda \cdot d$ ），来提高 cost 在决策过程中的权重